The invention generally relates to digital communication and in particular to methods, systems, and computer program products for sequentially decoding a received data signal.
While demands in terms of services and applications have known a dramatic growth over the past decades, major advances have been achieved to adapt communication systems to such demands. Modern communication systems include wireless communication systems which provide users access to one or more resources (e.g., bandwidth, transmit power, etc.). Different wireless communication systems are available today, such as the cellular and wireless ad-hoc networks accommodating single or multiple transmitters/receivers using single or multiple antennas, such as MIMO (Multiple Input-Multiple Output) systems. MIMO communication systems increase data transmission rates by exploiting space and time dimensions for communicating data over a multiplicity of antennas and during a multiplicity of time slots.
A major challenge of wireless communication systems is the decoding of the received signals. Indeed, in a wireless communication system, the signals transmitted to one or more receivers are conveyed in a transmission channel affected by fading, interference and noise. The signals received by a receiver can thus be disturbed. A decoder is thus required to decode the original desired signal correctly.
A decoder estimates the original data conveyed by one or multiple transmitters from the received signal by comparing the received vector of information symbols with possible vectors of transmitted symbols. Several decoding approaches can be used depending on the required performance level and processing capabilities of receivers. The optimal decoding approach for uniformly distributed information symbols is known as the maximum-likelihood (ML) decoding. It provides the minimum probability of detection error. According to a ML decoder, the vector of information symbols that is closest to the received signal is favored (i.e. vector having the minimum Euclidean Distance with respect to the received signal).
One implementation of the ML decoding criterion uses an exhaustive search over all the possible values in the constellation alphabet. This method provides optimal performance. However, it requires a high complexity that increases as the size of the constellation codebook or the number of the transmit antennas becomes higher, thereby making the implementation of such techniques impossible in practical systems. The implementation of such ML decoding techniques is thus impossible in practical systems requiring a high constellation order to guarantee a high spectral efficiency as well as an increasing number of antennas for ensuring a higher diversity order.
Other ML criterion-based decoding techniques have been proposed to properly decode the received signal while considering the decoder complexity, such as the Sphere Decoder (“E. Viterbo and J. Boutros. A universal lattice code decoder for fading channels. IEEE Transactions on Information Theory, 45(5):1639-1642, July 1999”) or the Schnorr-Euchner decoder (“C. P. Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. In Math. Programming, pages 181-191, 1993”). However, these decoders have an increasing complexity as the constellation size or the number of antennas increases. Other suboptimal low-complexity decoders, such as the ZF (Zero-Forcing), the ZF-DFE (Zero Forcing-Decision Feedback Equalizer) and the MMSE (Minimum Mean Square Error) decoder are implemented in practical systems but present poor performances in terms of the achievable diversity order and on the error performance.
Still other decoding algorithms applicable in linear communication systems, using single or multiple users and/or single or multiple antennas, include the lattice sequential decoders (such as the “stack” decoder) which implement the optimal ML decoding criterion using a tree representation of the ML optimization problem (decoding tree) and a tree search. Such decoding algorithms provide a reduced complexity with respect to the exhaustive search approach. According to the search strategy implemented by sequential decoders, the expanded tree nodes are stored in a global stack. In particular, the stack decoder stores, in the global stack, the tree nodes expanded during the decoding process and sorts them according to an increasing order of their decoding metrics.
Sequential decoders include decoders implementing a Best-First tree search such as the Stack decoder as disclosed in:                “A. R. Murugan, H. El-Gamal, M.-O. Damen, and G. Caire. A unified framework for tree search decoding: Rediscovering the sequential decoder. IEEE Transactions on Information Theory, 52(3):933-953, March 2006”;        “F. Jelinek. Fast sequential decoding algorithm using a stack. IBM J. Res. Dev., 13(6):675-685, November 1969”.        
Another type of lattice sequential decoding method using a Best-First tree search is known as the Fano decoding method as disclosed in “R. Fano. A heuristic discussion of probabilistic decoding. IEEE Transactions on Information Theory, 9(2):64-74, April 1963”.
Sequential decoders improve the overall decoding complexity. However, for an increasing constellation size and a high number of antennas, the stack decoding technique requires a high computational complexity. In order to reduce this complexity, another decoding technique referred to as the Spherical-Bound Stack decoder (SB-Stack) has been proposed in the article by G. R. Ben-Othman, R. Ouertani, and A. Salah, entitled “The Spherical Bound Stack Decoder”, In Proceedings of International Conference on Wireless and Mobile Computing, pages 322-327, October 2008. The SB-stack approach combines the Stack search strategy with the Sphere Decoder search region: the decoder searches for the closest vector inside a sphere centered at the received point implementing the stack decoding strategy. The spherical search region imposes a search interval for each decoded symbol. Only nodes belonging to these intervals at each tree level are visited and expanded.
Lattice sequential decoders have strongly imposed themselves as optimal decoding schemes in linear wireless communication systems reducing the optimal ML decoding problem to the search for the path in a graph-tree having the least cumulated metric.
In a conventional sequential decoder, to determine a best fit (path), a value depending on the ML metric is assigned to each node in the tree (called “metric”).
In some conventional approaches, the path metric for each node at a given level k of the decoding tree may be reduced of a term “b×k” which depends on a bias term b and on the level k.
The bias term allows controlling the amount of computations performed by the decoder. Also, the bias term makes it possible to achieve performance-complexity tradeoffs of the decoder.
With the introduction of a bias term b in the ML metric, parameterized sequential decoders including the Stack, Fano and SB-Stack decoders, offer a flexibility in terms of performance-complexity tradeoff. However, the selection of the bias in spatially multiplexed and coded MIMO systems is generally fixed deterministically without taking into account the channel statistics or the noise level. In other approaches using convolutional codes, such as the approach disclosed in “R. Fano. A heuristic discussion of probabilistic decoding. IEEE Transactions on Information Theory, 9(2):64-74, April 1963”, an optimized value for the bias is defined which corresponds to the coding rate of the underlying code. For convolutional lattice coding joint to Tomlinson-Harashima shaping, as described in “O. Shalvi, N. Sommer, and M. Feder, Signal codes: Convolutional lattice codes, IEEE Transactions on Information Theory, 57(8):5203-5226, August 2011”, the optimized value of the bias for high SNR regime is defined as
            σ      2        ⁢          log      ⁡              (                  4                      πσ            2                          )              ,with σ2 designating the variance of the additive noise affecting the transmission channel.
However, in the existing approaches, the value of the bias parameter is the same for all the tree levels. This results in an insufficient flexibility in terms of performance/complexity.